import java.util.ArrayList;
import java.util.List;

/**
 * @author LKQ
 * @date 2022/2/19 12:09
 * @description 回溯
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.subsets(new int[]{1, 2, 3});
    }
    List<Integer> t = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        // 取当前的数
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        // 移除最后一个数，也就是不取，取下一个数
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }

}
